#include "../tools.h"

int findKth(vector<int>& nums1, vector<int>& nums2, int k){
    int size1 = nums1.size();
    int size2 = nums2.size();
    int index1 = 0, index2 = 0;
    while(true){
        if(k == 1) return min(nums1[index1], nums2[index2]);
        if(index1 == size1) return nums2[index2 + k - 1];
        if(index2 == size2) return nums1[index1 + k - 1];

        int newindex1 = min(index1 + k / 2 - 1, size1 - 1);
        int newindex2 = min(index2 + k / 2 - 1, size2 - 1);
        if(nums1[newindex1] <= nums2[newindex2]){
            k -= newindex1 - index1 + 1;
            index1 = newindex1 + 1;
        }
        else{
            k -= newindex2 - index2 + 1;
            index2 = newindex2 + 1;
        }
    }
}


int main(int argc, char const *argv[])
{
    vector<int> nums1 = {1};
    vector<int> nums2 = {2,3,4,5,6};

    cout << findKth(nums1, nums2, 6);

    return 0;
}
